(寒假开黑gym)2018 ACM-ICPC, Syrian Collegiate Programming Contest

Diposting di | Edited on

传送门

付队！

许老师！

Hello SCPC 2018! (签到)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
struct node{
    int value,id;
}a[maxn];
int cmp(node a,node b){
    return a.value<b.value;
}
int f[maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    freopen("hello.in","r",stdin);
    int t;
    cin>>t;
    while(t--){
        for(int i=1;i<=12;i++)cin>>a[i].value,a[i].id=i;
        sort(a+1,a+1+12,cmp);
        memset(f,0,sizeof(f));
        for(int i=1;i<=4;i++)f[a[i].id]=i;
        int flag=0;
        for(int i=1;i<=4;i++){
            if(f[i]!=i){
                flag=1;
            }
        }
        if(flag)cout<<"no"<<endl;
        else cout<<"yes"<<endl;
    }
    return 0;
}

Binary Hamming (签到)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
char s[maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    freopen("hamming.in","r",stdin);
    int t;
    cin>>t;
    while(t--){
        int n,a1=0,b1=0,a2=0,b2=0;
        cin>>n;
        cin>>s;
        for(int i=0;i<n;i++)if(s[i]=='1')a1++;else b1++;
        cin>>s;
        for(int i=0;i<n;i++)if(s[i]=='1')a2++;else b2++;
        cout<<min(a1,b2)+min(b1,a2)<<endl;
    }
    return 0;
}

Portals (模拟,分类讨论)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=2e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
char s[maxn];
int dx[2]={1,-1};
int n;
int S,T;
int dfs(int x,int i){
    if(x==n+1)return 0;
    if(x==0)return 0;
    if(s[x]=='#')return 0;
    if(s[x]=='o')return 1;
    if(s[x]=='s'||s[x]=='e')return 1;
    return dfs(x+dx[i],i);
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    freopen("portals.in","r",stdin);
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=0;i<=n+10;i++)s[i]='#';
        cin>>s+1;
        int len=strlen(s+1);
        for(int i=1;i<=n;i++){
            if(s[i]=='s')S=i;
            if(s[i]=='e')T=i;
        }
        int neds=dfs(S+1,0)+dfs(S-1,1);
        int nedt=dfs(T+1,0)+dfs(T-1,1);
        int ans=1e9;
        if(s[S-1]=='o'||s[S+1]=='o'||s[S-1]=='e'||s[S+1]=='e')neds=1e9;
        if(s[T-1]=='o'||s[T+1]=='o'||s[T-1]=='s'||s[T+1]=='s')nedt=1e9;
        ans=min(neds,nedt);
        if(ans==1e9)cout<<-1<<endl;
        else cout<<ans<<endl;
    }
    return 0;
}

Carnival Slots （DP，记忆化搜索）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
char mp[550][550];

ll dp[505][505];
ll num[550];
ll value[550];
int r,c;

ll dfs(int x,int y){
    if(x==r+1){
        return value[y];
    }
    if(dp[x][y]!=-1)return dp[x][y];
    ll ans=0;
    ans=dfs(x+1,y);

    if(y-1>=1&&mp[x][y]!='.')ans=max(ans,dfs(x+1,y-1));
    if(y+1<=c&&mp[x][y]!='.')ans=max(ans,dfs(x+1,y+1));
    return dp[x][y]=ans;
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    freopen("balls.in","r",stdin);
    int t;
    cin>>t;
    while(t--){
        cin>>r>>c;
        for(int i=1;i<=c;i++)cin>>num[i];
        for(int i=1;i<=r;i++){
            cin>>mp[i]+1;
        }
        for(int i=1;i<=c;i++)cin>>value[i];
        ll ans=0;
        memset(dp,-1,sizeof(dp));
        for(int i=1;i<=c;i++){
            ans+=dfs(1,i)*num[i]*1LL;
        }
        cout<<ans<<endl;
    }
    return 0;
}

Bugged System (模拟)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=2e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int x[maxn];
struct node{
    int s,d;
}my[maxn];
int in[maxn];
int out[maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    freopen("bugged.in","r",stdin);
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)cin>>x[i];
        ll ans=0;
        for(int i=1;i<=m;i++){
            cin>>my[i].s>>my[i].d;
            in[my[i].s]++;
            out[my[i].d]++;
            ans+=abs(x[my[i].s]-x[my[i].d]);
        }
        bool f=0;
        for(int i=1;i<=n;i++){
            if(in[i]!=out[i])f=1;
            in[i]=out[i]=0;
        }
        if(f)cout<<"-1"<<endl;
        else cout<<ans<<endl;
    }
    return 0;
}

Tourists’ Tour (染色问题，拓扑)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
vector<int>ve[maxn];
void add(int u,int v){
    ve[v].push_back(u);
    ve[u].push_back(v);
}
int color[maxn];
int vis[10];
int mx;
void dfs(int now){
   // cout<<"now="<<now<<endl;
    memset(vis,0,sizeof(vis));
    for(int i=0;i<ve[now].size();i++){
        vis[color[ve[now][i]]]=1;
    }
    for(int i=1;i<10;i++){
        if(!vis[i]){
            color[now]=i;
            break;
        }
    }
    mx=max(mx,color[now]);
    for(int i=0;i<ve[now].size();i++)if(!color[ve[now][i]])dfs(ve[now][i]);
}
int a[maxn];

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    freopen("tour.in","r",stdin);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i],ve[i].clear();
		stack<int>pq;
		pq.push(1);
		for(int i=2;i<=n;i++){
            while(!pq.empty()&&a[pq.top()]<a[i])pq.pop();
            if(!pq.empty()){
                add(pq.top(),i);
            }
            pq.push(i);
		}
		stack<int>q;
		q.push(n);
		for(int i=n-1;i>=1;i--){
            while(!q.empty()&&a[q.top()]<a[i])q.pop();
            if(!q.empty()){
                add(q.top(),i);
            }
            q.push(i);
		}
		for(int i=1;i<=n;i++)reverse(ve[i].begin(),ve[i].end());
		for(int i=1;i<=n;i++)color[i]=0;
		mx=0;
		for(int i=1;i<=n;i++)if(color[i]==0)dfs(i);
		cout<<mx<<endl;
		for(int i=1;i<=n;i++)cout<<color[i]<<" ";
		cout<<endl;
    }
    return 0;
}

Is Topo Logical? (模拟)

Rise of the Robots (最小圆覆盖)

思路

首先感谢付队的模板！太快了

这题可以把题意转化成求点到所有直线距离的最短距离,然后为什么答案要取反呢，因为我们一开始是以原点为起点的

然后答案给出的是圆心为起点的，所以我们要把这个起点缩回原点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
#define mp make_pair
const double eps=1e-8;
const double pi=4*atan(1.0);
struct point{
    double x,y;
    point(double a=0,double b=0):x(a),y(b){}
};
int dcmp(double x){ return fabs(x)<eps?0:(x<0?-1:1);}
point operator +(point A,point B) { return point(A.x+B.x,A.y+B.y);}
point operator -(point A,point B) { return point(A.x-B.x,A.y-B.y);}
point operator *(point A,double p){ return point(A.x*p,A.y*p);}
point operator /(point A,double p){ return point(A.x/p,A.y/p);}
point rotate(point A,double rad){
    return point(A.x*cos(rad)-A.y*sin(rad), A.x*sin(rad)+A.y*cos(rad));
}
bool operator ==(const point& a,const point& b) {
     return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;
}
double dot(point A,point B){ return A.x*B.x+A.y*B.y;}
double det(point A,point B){ return A.x*B.y-A.y*B.x;}
double dot(point O,point A,point B){ return dot(A-O,B-O);}
double det(point O,point A,point B){ return det(A-O,B-O);}
double length(point A){ return sqrt(dot(A,A));}
double angle(point A,point B){ return acos(dot(A,B)/length(A)/length(B));}
double distoline(point P,point A,point B)
{
    //点到直线距离
    point v1=B-A,v2=P-A;
    return fabs(det(v1,v2)/length(v1));
}
double distoseg(point P,point A,point B)
{
    //点到线段距离
    if(A==B) return length(P-A);
    point v1=B-A,v2=P-A,v3=P-B;
    if(dcmp(dot(v1,v2))<0) return length(v2);
    else if(dcmp(dot(v1,v3))>0) return length(v3);
    return fabs(det(v1,v2)/length(v1));
}
double Ployarea(vector<point>p)
{
    //多边形面积
    double ans=0; int sz=p.size();
    for(int i=1;i<sz-1;i++) ans+=det(p[i]-p[0],p[i+1]-p[0]);
    return ans/2.0;
}
bool SegmentProperIntersection(point a1,point a2,point b1,point b2)   {
    //规范相交
    double c1=det(a2-a1,b1-a1),c2=det(a2-a1,b2-a1);
    double c3=det(b2-b1,a1-b1),c4=det(b2-b1,a2-b1);
    return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;
}
bool isPointOnSegment(point p,point a1,point a2)
{
    //点是否在线段上
    return dcmp(det(a1-p,a2-p)==0&&dcmp(dot(a1-p,a2-p))<0);
}
int isPointInPolygon(point p,vector<point>poly)
{
    //判断点与多边形的位置关系
    int wn=0,sz=poly.size();
    for(int i=0;i<sz;i++){
        //在边上
        if(isPointOnSegment(p,poly[i],poly[(i+1)%sz])) return -1;
        int k=dcmp(det(poly[(i+1)%sz]-poly[i],p-poly[i]));
        int d1=dcmp(poly[i].y-p.y); int d2=dcmp(poly[(i+1)%sz].y-p.y);
        if(k>0&&d1<=0&&d2>0) wn++;
        if(k<0&&d2<=0&&d1>0) wn--;
    }
    if(wn!=0) return 1;//内部
    return 0;          //外部
}
double seg(point O,point A,point B){
    if(dcmp(B.x-A.x)==0) return (O.y-A.y)/(B.y-A.y);
    return (O.x-A.x)/(B.x-A.x);
}
pair<double,int>s[110*60];
double polyunion(vector<point>*p,int N){ //有多个才加*,单个不加，有改变的加&
    //求多边形面积并
    double res=0;
    for(int i=0;i<N;i++){
        int sz=p[i].size();
        for(int j=0;j<sz;j++){
            int m=0;
            s[++m]=mp(0,0);
            s[++m]=mp(1,0);
            point a=p[i][j],b=p[i][(j+1)%sz];
            for(int k=0;k<N;k++){
                if(i!=k){
                    int sz2=p[k].size();
                    for(int ii=0;ii<sz2;ii++){
                        point c=p[k][ii],d=p[k][(ii+1)%sz2];
                        int c1=dcmp(det(b-a,c-a));
                        int c2=dcmp(det(b-a,d-a));
                        if(c1==0&&c2==0){
                            if(dcmp(dot(b-a,d-c))){
                                s[++m]=mp(seg(c,a,b),1);
                                s[++m]=mp(seg(c,a,b),-1);
                            }
                        }
                        else{
                            double s1=det(d-c,a-c);
                            double s2=det(d-c,b-c);
                            if(c1>=0&&c2<0) s[++m]=mp(s1/(s1-s2),1);
                            else if(c1<0&&c2>=0) s[++m]=mp(s1/(s1-s2),-1);
                        }
                    }
                }
            }
            sort(s+1,s+m+1);
            double pre=min(max(s[1].first,0.0),1.0),now,sum=0;
            int cov=s[0].second;
            for(int j=2;j<=m;j++){
                now=min(max(s[j].first,0.0),1.0);
                if(!cov) sum+=now-pre;
                cov+=s[j].second;
                pre=now;
            }
            res+=det(a,b)*sum;
        }
    }
    return -(res/2);
}
point jiaopoint(point p,point v,point q,point w)
{   //p+tv q+tw，点加向量表示直线，求直线交点
    point u=p-q;
    double t=det(w,u)/det(v,w);
    return p+v*t;
}
point GetCirPoint(point a,point b,point c)
{
    point p=(a+b)/2;    //ad中点
    point q=(a+c)/2;    //ac中点
    point v=rotate(b-a,pi/2.0),w=rotate(c-a,pi/2.0);   //中垂线的方向向量
    if (dcmp(length(det(v,w)))==0)    //平行
    {
        if(dcmp(length(a-b)+length(b-c)-length(a-c))==0) return (a+c)/2;
        if(dcmp(length(b-a)+length(a-c)-length(b-c))==0) return (b+c)/2;
        if(dcmp(length(a-c)+length(c-b)-length(a-b))==0) return (a+b)/2;
    }
    return jiaopoint(p,v,q,w);
}
point MinCircular(point *P,int n)
{
    //最小圆覆盖 ,看起来是O(N^3)，期望复杂度为O(N)
    random_shuffle(P+1,P+n+1);    //随机化
    point c=P[1]; double r=0;   //c 圆心,,//r 半径
    for (int i=2;i<=n;i++)
        if (dcmp(length(c-P[i])-r)>0)    //不在圆内
        {
            c=P[i],r=0;
            for (int j=1;j<i;j++)
                if (dcmp(length(c-P[j])-r)>0)
                {
                    c=(P[i]+P[j])/2.0;
                    r=length(c-P[i]);
                    for (int k=1;k<j;k++)
                        if (dcmp(length(c-P[k])-r)>0)
                        {
                            c=GetCirPoint(P[i],P[j],P[k]);
                            r=length(c-P[i]);
                        }
                }
        }
    //cout<<r<<":"<<c.x<<" "<<c.y<<endl;
    return c;
}
const int maxn=400010;
bool cmp(point a,point b){ return a.x==b.x?a.y<b.y:a.x<b.x; }
point f[maxn],c[maxn],ch[maxn];
void convexhull(point *a,int n,int &top)
{
    //水平序的Andrew算法求凸包。
    sort(a+1,a+n+1,cmp); top=0;
    for(int i=1;i<=n;i++){ //求下凸包
        while(top>=2&&det(ch[top-1],ch[top],a[i])<=0) top--;
        ch[++top]=a[i];
    }
    int ttop=top;
    for(int i=n-1;i>=1;i--){ //求上凸包
        while(top>ttop&&det(ch[top-1],ch[top],a[i])<=0) top--;
        ch[++top]=a[i];
    }
}
void P(double x)
{
    //if(fabs(x)<0.000001) puts("0.00000000"); else
    printf("%.9lf",x);
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    freopen("robots.in","r",stdin);
    int t;
    cin>>t;
    while(t--){
        int n,R,r;
        cin>>n>>R>>r;
        int tot=1;
        f[tot].x=0;f[tot].y=0;
        for(int i=1;i<=n;i++){
            int a,b;cin>>a>>b;
            tot++;
            f[tot].x=f[tot-1].x+a;
            f[tot].y=f[tot-1].y+b;
        }
        point anw=MinCircular(f,tot);
        cout<<fixed<<setprecision(9);
        cout<<-anw.x<<" "<<-anw.y<<endl;
    }
    return 0;
}